CF446C DZY Loves Fibonacci Numbers <线段树>

Problem

DZY Loves Fibonacci Numbers

Description

In mathematical terms, the sequence of is defined by the recurrence relation .
loves Fibonacci numbers very much. Today gives you an array consisting of integers: . Moreover, there are queries, each query has one of the two types:

Format of the query “ ”. In reply to the query, you need to add to each element , where .
Format of the query “ ”. In reply to the query you should output the value of modulo .

Help reply to all the queries.

Input

The first line of the input contains two integers and . The second line contains n integers — initial array .
Then, lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality holds.

Output

For each query of the second type, print the value of the sum on a single line.

Example

Input

Output

1
2

17
12

Note

After the first query, .
For the second query, .
After the third query, .
For the fourth query, .

标签：线段树

Translation

给出一个长为级别的初始数组，要求维护两种操作：

将中的每个数对应加上从的斐波那契数，即使加上
询问模的值

Solution

不难想到此题需要用线段树维护。不过难点在于如何合并标记。

初步想法是每次打标记时记录下此区间是从斐波那契数列的多少项开始一一对应地加进去，不过这样是无法合并标记的，每个结点只能有一个标记，可以被卡成。

考虑把标记换一种存法。对于一个数列，我们将其称为一个“伪斐波那契数列”，不难发现其等于几个斐波那契数列的子序列之和，即在原题中，不管如何加，每个区间最后加的数列都是一个伪斐波那契数列。而此序列可以仅通过最前面的两项和推出后面的任意项以及前若干项之和，即

用这两个公式我们可以计算任意项及前任意项的和。
每个标记为一个数对，那么合并标记的时候将两个标记的和分别相加，得到即可。
总时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define mid ((s+t)>>1)
#define MOD 1000000009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;	lnt fib[MAX_N+5] = {0LL, 1LL};
struct node {lnt c, f1, f2;} tr[(MAX_N<<2)+5];
lnt fn(lnt f1, lnt f2, int len) {return len == 1 ? f1 : (len == 2 ? f2 : (f1*fib[len-2]%MOD+f2*fib[len-1]%MOD)%MOD);}
lnt sum(lnt f1, lnt f2, int len) {return len == 1 ? f1 : (len == 2 ? (f1+f2)%MOD : (fn(f1, f2, len+2)-f2+MOD)%MOD);}
void updata(int v) {tr[v].c = (tr[v<<1].c+tr[v<<1|1].c)%MOD;}
void downtag(int v, int s, int t) {
    if (!tr[v].f1) return;
    lnt lf1 = tr[v].f1, lf2 = tr[v].f2, rf1 = fn(lf1, lf2, mid-s+2), rf2 = fn(lf1, lf2, mid-s+3);
    (tr[v<<1].f1 += lf1) %= MOD, (tr[v<<1].f2 += lf2) %= MOD, (tr[v<<1].c += sum(lf1, lf2, mid-s+1)) %= MOD;
    (tr[v<<1|1].f1 += rf1) %= MOD, (tr[v<<1|1].f2 += rf2) %= MOD, (tr[v<<1|1].c += sum(rf1, rf2, t-mid)) %= MOD;
    tr[v].f1 = tr[v].f2 = 0;
}
void build(int v, int s, int t) {
    if (s == t) {read(tr[v].c); return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    updata(v);
}
void modify(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        (tr[v].f1 += fib[s-l+1]) %= MOD, (tr[v].f2 += fib[s-l+2]) %= MOD;
        (tr[v].c += sum(fib[s-l+1], fib[s-l+2], t-s+1)) %= MOD;	return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(v<<1, s, mid, l, r);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
    updata(v);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].c;
    lnt ret = 0;	downtag(v, s, t);
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= MOD;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= MOD;
    updata(v);	return ret;
}
void init() {for (int i = 2; i <= MAX_N; i++) fib[i] = (fib[i-2]+fib[i-1])%MOD;}
int main() {
    read(n), read(m), init(), build(1, 1, n);
    while (m--) {
        int opt, l, r;	read(opt), read(l), read(r);
        if (opt == 1) modify(1, 1, n, l, r);
        else printf("%I64d\n", query(1, 1, n, l, r));
    }
    return 0;
}